package ext;
import java.util.*;
import org.junit.*;

import util.ArrayGenerator;

public class UnionSortedArrays {

    public static int[] union(int[] n1, int[] n2) {
        int m = n1.length, n = n2.length;
        if (m > n) {
            return union(n2, n1);
        }
        int i = 0, j = 0;
        List<Integer> res = new ArrayList<>();
        for (int k = 0; k < m; k++) {
            if (n1[i] == n2[j]) {
                res.add(n1[i]);
                i++;
                j++;
            } else if (n1[i] < n2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    @Test
    public void test() {
        for (int i = 0; i < 1000000; i++) {
            int[] n1 = ArrayGenerator.getArray(100, 100);
            Arrays.sort(n1);
            int[] n2 = ArrayGenerator.getArray(100, 100);
            Arrays.sort(n2);
            int[] res = union(n1, n2);
            String s1 = Arrays.toString(res);
            Arrays.sort(res);
            String s2 = Arrays.toString(res);
            if (!s1.equals(s2)) {
                System.out.println("false");
            }
        }
        System.out.println("finish");
    }

}
